We study the appearance of powers of Hamilton cycles in pseudorandom\udgraphs, using the following comparatively weak pseudorandomness notion.\udA graph G is (ε, p, k, ℓ)-pseudorandom if for all disjoint X and Y ⊆ V (G)\udwith |X| ≥ εpkn and |Y | ≥ εpℓn we have e(X, Y ) = (1 ± ε)p|X||Y |. We prove\udthat for all β > 0 there is an ε > 0 such that an (ε, p, 1, 2)-pseudorandom graph\udon n vertices with minimum degree at least βpn contains the square of a Hamilton\udcycle. In particular, this implies that (n, d, λ)-graphs with λ ≪ d5/2n−3/2\udcontain the square of a Hamilton cycle, and thus a triangle factor if n is a\udmultiple of 3. This improves on a result of Krivelevich, Sudakov and Szab´o\ud[Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004),\udno. 3, 403–426].\udWe also extend our result to higher powers of Hamilton cycles and establish\udcorresponding counting versions.
展开▼
机译：我们使用以下相对较弱的伪随机概念研究伪随机\ udgraph中哈密顿循环的幂的出现。\ ud对于所有不相交的X和Y⊆V（G），图G为（ε，p，k，ℓ）-伪随机\ udwith | X | ≥εpkn和| Y | ≥εpℓn我们有e（X，Y）=（1±ε）p | X || Y |。我们证明\ ud所有β> 0都存在ε> 0，使得（ε，p，1，2）-伪随机图\最小度数为n的n个顶点至少包含一个Hamilton \ udcycle的平方。尤其是，这意味着具有λd5 / 2n-3 / 2 \ ud的（n，d，λ）图包含汉密尔顿循环的平方，因此如果n是3的倍数，则包含三角形因子。关于Krivelevich，Sudakov和Szab´o \ ud [稀疏伪随机图中的三角因子，Combinatorica 24（2004），\ udno。 [3，403–426]。\ ud我们还将结果扩展到汉密尔顿循环的高次幂，并建立\相应的计数版本。
展开▼
